package com.github.yangyishe.p300;

/**
 * 215. 数组中的第K个最大元素
 * https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
 * 输出: 4
 *
 *
 * 提示：
 *
 * 1 <= k <= nums.length <= 105
 * -104 <= nums[i] <= 104
 */
public class Problem215 {
    public static void main(String[] args) {
        int[] nums=new int[]{-1,2,0};
        int k=1;

        Problem215 problem215 = new Problem215();
        int largest = problem215.findKthLargest(nums, k);
        System.out.println("largest = " + largest);
    }

    /**
     * 堆应用中最经典的top-k问题
     * 参考: https://www.hello-algo.com/chapter_heap/top_k/#832
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        //1. 初始化一个小顶堆, size=k
        int[] heap=new int[k];

        //2. 将数组的前k个元素依次入堆. 堆顶元素表示第k大个元素
        for(int i=0;i<k;i++){
            heap[i]=nums[i];
        }
        createMinHeap(heap);

        //3. 从第k+1个元素开始, 与堆顶元素比较. 如果当前元素比堆顶元素大, 则删除堆顶元素, 并将该院入堆
        for(int i=k;i<nums.length;i++){
            if(nums[i]>heap[0]){
                heap[0]=nums[i];
                siftDown(heap,0);
            }
        }

        //4. 遍历完成后, 堆顶的元素即为最大的第k个元素
        return heap[0];
    }



    private void createMinHeap(int[] heap){
        for(int i=heap.length-1;i>=0;i--){
            siftDown(heap,i);
        }
    }

//    private void siftDown(int[] heap, int i) {
//        while(true){
//            int parentIndex=(i-1)/2;
//            if(parentIndex<0){
//                return;
//            }
//            if(heap[parentIndex]>heap[i]){
//                swap(heap,parentIndex,i);
//                i=parentIndex;
//            }else{
//                return;
//            }
//
//        }
//    }

    private void swap(int[] heap,int i,int j){
        int temp=heap[j];
        heap[j]=heap[i];
        heap[i]=temp;
    }

    private void siftDown(int[] heap, int i) {
        while(true){
            int minBot;
            int left=i*2+1;
            int right=i*2+2;
            if(left>=heap.length&&right>=heap.length){
                return;
            }
            if(left>=heap.length){
                minBot=right;
            }else if(right>=heap.length){
                minBot=left;
            }else{
                minBot=heap[left]<heap[right]?left:right;
            }

            if(heap[minBot]>=heap[i]){
                return;
            }
            swap(heap,minBot,i);
            i=minBot;
        }
    }


}
